home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93c.txt / 000025_icon-group-sender _Mon Jul 19 04:34:06 1993.msg < prev    next >
Internet Message Format  |  1994-02-02  |  3KB
  1. Received: by cheltenham.cs.arizona.edu; Thu, 22 Jul 1993 12:26:30 MST
  2. Date: 19 Jul 93 04:34:06 GMT
  3. From: cis.ohio-state.edu!math.ohio-state.edu!darwin.sura.net!haven.umd.edu!cs.umd.edu!uchinews!quads!goer@ucbvax.Berkeley.EDU  (Richard L. Goerwitz)
  4. Organization: University of Chicago
  5. Subject: new sortff
  6. Message-Id: <1993Jul19.043406.17331@midway.uchicago.edu>
  7. Sender: icon-group-request@cs.arizona.edu
  8. To: icon-group@cs.arizona.edu
  9. Status: R
  10. Errors-To: icon-group-errors@cs.arizona.edu
  11.  
  12. As promised:
  13.  
  14. ############################################################################
  15. #
  16. #    Name:     sortff.icn
  17. #
  18. #    Title:     sortf with multiple field arguments
  19. #
  20. #    Author:     Bob Alexander and Richard L. Goerwitz
  21. #
  22. #    Date:    July 14, 1993
  23. #
  24. ############################################################################
  25. #
  26. #  Sortff is like sortf(), except takes an unlimited number of field
  27. #  arguments.  E.g. if you want to sort a list of structures on field
  28. #  5, and (for those objects that have the same field 5) do a sub-sort
  29. #  on field 2, you would use "sortff(list_of_objects, 5, 2)."
  30. #
  31. ############################################################################
  32.  
  33. #
  34. # sortff:  structure [x integer [x integer...]] -> structure
  35. #          (L, fields...) -> new_L
  36. #
  37. #     Where L is any subscriptable structure, and fields are any
  38. #     number of integer subscripts in any desired order.  Returns
  39. #     a copy of structure L with its elements sorted on fields[1],
  40. #     and, for those elements having an identical fields[1], sub-
  41. #     sorted on field[2], etc.
  42. #
  43. procedure sortff(L, fields[])
  44.     *L <= 1 & { return copy(L) }
  45.     return sortff_1(L, fields, 1, [])
  46. end
  47.  
  48. procedure sortff_1(L, fields, k, uniqueObject)
  49.  
  50.     local sortField, cachedKeyValue, i, startOfRun, thisKey
  51.  
  52.     sortField := fields[k]
  53.     L := sortf(L, sortField)    # initial sort using fields[k]
  54.     #
  55.     #  If more than one sort field is given, use each field successively
  56.     #  as the current key, and, where members in L have the same value for
  57.     #  this key, do a subsort using fields[k+1].
  58.     #
  59.     if fields[k +:= 1] then {
  60.         #
  61.         #  Set the equal-key-run pointer to the start of the list and
  62.         #  save the value of the first key in the run.
  63.         #
  64.     startOfRun := 1
  65.     cachedKeyValue := L[startOfRun][sortField] | uniqueObject
  66.     every i := 2 to *L do {
  67.         thisKey := L[i][sortField] | uniqueObject
  68.         if not (thisKey === cachedKeyValue) then {
  69.             #
  70.             # We have an element with a sort key different from the
  71.             # previous.  If there's a run of more than one equal keys,
  72.             # sort the sublist.
  73.             #
  74.         if i - startOfRun > 1 then {
  75.             L := L[1:startOfRun] |||
  76.              sortff_1(L[startOfRun:i], fields, k, uniqueObject) |||
  77.              L[i:0]
  78.         }
  79.             # Reset the equal-key-run pointer to this key and cache.
  80.         startOfRun := i
  81.         cachedKeyValue := L[startOfRun][sortField] | uniqueObject
  82.             }
  83.     }
  84.     #
  85.     #  Sort a final run if it exists.
  86.     #
  87.     if i - startOfRun > 1 then {
  88.         L := L[1:startOfRun] |||
  89.          sortff_1(L[startOfRun:0], fields, k, uniqueObject)
  90.     }
  91.     }
  92.  
  93.     return L
  94.  
  95. end
  96. -- 
  97.  
  98.    -Richard L. Goerwitz              goer%midway@uchicago.bitnet
  99.    goer@midway.uchicago.edu          rutgers!oddjob!ellis!goer
  100.